Technologies are disclosed herein for executing commands within virtual machine (“VM”) instances. A public web service application programming interface (“API”) is exposed within a service provider network that includes methods relating to the execution of commands within VM instances. For example, the API might include a method for obtaining a list of the commands that can be executed within a VM instance. The API might also include a method for requesting the execution of a command within a VM instance. The API might also include a method for requesting data describing the status of the execution of a command within a VM instance. The API might also expose other methods. A software agent executing on a VM instance may be utilized to provide a list of commands that can be executed in the VM, to execute requested commands, and to provide data describing the status of execution of a command.