Federated learning is used for decentralized training of machine learning models on millions of edge mobile devices. This is challenging because these devices often have limited communication bandwidth, and local computation resources. We exploit partially trainable neural networks, which freeze a portion of the model parameters during the entire training process, to reduce the communication cost with little implications on model performance. Through extensive experiments, we empirically show that Federated learning of Partially Trainable neural networks (FedPT) can result in good communication-accuracy trade-offs, with up to $46\times$ reduction in communication cost, at a small accuracy cost. The proposed FedPT can be particularly interesting for pushing the limitations of overparameterization for on-device learning.