NOTE: Recently the azure cli has changed to the az cli, unless you have the older azure cli tools still installed, you should visit the new and updated post with instructions for the az cli here.

Unless you are still using the old azure cli tool, the instructions bellow will not work in the new az cli.

Before moving further, please, make sure you have the Azure CLI tools installed:
Install the Azure CLI

For the steps to work properly, please, make sure you are logged in to the Azure CLI:
Connect to an Azure subscription from the Azure Command-Line Interface (Azure CLI)

For basic Azure CLI commands in Resource Manager (ARM), please also check this article:
Use the Azure CLI for Mac, Linux, and Windows with Azure Resource Manager

In this example, the following variables will be used:

Resource Group: ARMGROUP
Original VM Name: LinuxVM
Location: southcentralus
NIC Name: LinuxVM-NIC
Storage Account: ARMSTORAGE
VHD URI: https://ARMSTORAGE.blob.core.windows.net/vhds/linuxvm.vhd

If you want to keep some information from the VM before deleting:
azure config mode arm
azure vm show ARMGROUP LinuxVM > ORIGINAL_VM.txt

The output of the command will be similar to the fields below:

NOTE: Please, note that some information that we won’t need was removed in this case to make it easier.

info:    Executing command vm show
info:    Looking up the VM “LinuxVM”
info:    Looking up the NIC “LinuxVM-NIC”
info:    Looking up the public ip “LinuxVM”
…
…
data:    Name                            :LinuxVM
data:    Location                        :southcentralus
data:      Size                          :Standard_D1
data:        OSType                      :Linux
data:        Name                        :LinuxVM
data:        Vhd:
data:          Uri                       :https://ARMSTORAGE.blob.core.windows.net/vhds/linuxvm.vhd
data:      Computer Name                 :linuxvm
data:        Network Interface #1:
data:          Primary                   :true
data:          Name                      :LinuxVM-NIC
data:          Location                  :southcentralus
info:    vm show command OK

Deleting a VM on ARM using the CLI:
azure vm delete ARMGROUP LinuxVM

Recreating the VM from the Original VHD:
azure vm create -f LinuxVM-NIC -d https://ARMSTORAGE.blob.core.windows.net/vhds/linuxvm.vhd -o ARMSTORAGE -z Standard_D1 ARMGROUP LinuxVM southcentralus linux --disable-boot-diagnostics

After the command is executed you should be able to see the VM on the Azure Portal. You might need to re-enable diagnostics in the particular VM.