Methods, systems, and computer-readable media for placement optimization for virtualized graphics processing are disclosed. A provider network comprises a plurality of instance locations for physical compute instances and a plurality of graphics processing unit (GPU) locations for physical GPUs. A GPU location for a physical GPU or an instance location for a physical compute instance is selected in the provider network. The GPU location or instance location is selected based at least in part on one or more placement criteria. A virtual compute instance with attached virtual GPU is provisioned. The virtual compute instance is implemented using the physical compute instance in the instance location, and the virtual GPU is implemented using the physical GPU in the GPU location. The physical GPU is accessible to the physical compute instance over a network. An application is executed using the virtual GPU on the virtual compute instance.