Methods, systems, and apparatus, including computer programs encoded on computer storage media, for unmanned aerial vehicle authorization and geofence envelope determination. One of the methods includes maintaining, by a cloud system in wireless communication with Unmanned Aerial Vehicles (UAVs), allocated geofence envelopes for one or more of the UAVs, with each geofence envelope being a virtual barrier for a real-world geographic area. A request for approval of an updated geofence envelope is received from a first UAV in flight. The cloud system determines that the updated geofence envelope has not been allocated and/or the updated geofence envelope does not interfere with allocated geofence envelopes. In response to the determination, a response indicating approval of the request is generated. The generated response is provided to the first UAV.