To digitally decode phase and amplitude images of a sample from its hologram, auto-focusing and phase recovery steps are required, which are in general challenging to compute. Here, we demonstrate fast and robust autofocusing and phase recovery that are simultaneously performed using a deep convolutional neural network (CNN). This CNN is trained with pairs of randomly de-focused back-propagated holograms and their corresponding in-focus phase recovered images (used as ground truth). After its training, the CNN takes a single back-propagated hologram, and outputs an extended depth-of-field (DOF) complex-valued image, where all the objects or points-of-interest within the sample volume are autofocused and phase-recovered all in parallel. Compared to iterative image reconstruction or a CNN trained using only in-focus images, this new approach achieves >25-fold increase in image DOF and eliminates the need to autofocus individual points within the sample volume, thus improving the complexity of holographic image reconstruction from O(nm) to O(1), where n refers to the number of individual object points within the sample volume, and m represents the autofocusing search space. We demonstrated the success of this approach by imaging various samples, including aerosols and human breast tissue sections. Our results highlight some unique capabilities of deep-learning based image reconstruction methods that are powered by data.