For diagnosis and risk assessment in patients with stable ischemic heart disease, myocardial perfusion scintigraphy is one of the most common cardiological examinations performed today. There are however many motivations for why an artificial intelligence algorithm would provide useful input to this task. For example to reduce the subjectiveness and save time for the nuclear medicine physicians working with this time consuming task. In this work we have developed a deep learning algorithm for multi-label classification based on a convolutional neural network to estimate the probability of obstructive coronary artery disease in the left anterior artery, left circumflex artery and right coronary artery. The prediction is based on data from myocardial perfusion scintigraphy studies conducted in a dedicated Cadmium-Zinc-Telluride cardio camera (D-SPECT Spectrum Dynamics). Data from 588 patients was available, with stress images in both upright and supine position, as well as a number of auxiliary parameters such as angina symptoms and age. The data was used to train and evaluate the algorithm using 5-fold cross-validation. We achieve state-of-the-art results for this task with an area under the receiver operating characteristics curve of 0.89 as average on per-vessel level and 0.95 on per-patient level.