Computer-aided assessment of physical rehabilitation entails evaluation of patient performance in completing prescribed rehabilitation exercises, based on processing movement data captured with a sensory system. Despite the essential role of rehabilitation assessment toward improved patient outcomes and reduced healthcare costs, existing approaches lack versatility, robustness, and practical relevance. In this paper, we propose a deep learning-based framework for automated assessment of the quality of physical rehabilitation exercises. The main components of the framework are metrics for quantifying movement performance, scoring functions for mapping the performance metrics into numerical scores of movement quality, and deep neural network models for generating quality scores of input movements via supervised learning. The proposed performance metric is defined based on the log-likelihood of a Gaussian mixture model, and encodes low-dimensional data representation obtained with a deep autoencoder network. The proposed deep spatio-temporal neural network arranges data into temporal pyramids, and exploits the spatial characteristics of human movements by using sub-networks to process joint displacements of individual body parts. The presented framework is validated using a dataset of ten rehabilitation exercises. The significance of this work is that it is the first that implements deep neural networks for assessment of rehabilitation performance.