The composition and density of immune cells in the tumor microenvironment profoundly influence tumor progression and success of anti-cancer therapies. Flow cytometry, immunohistochemistry staining, or single-cell sequencing is usually not available such that we rely on computational methods to estimate the immune-cell composition from bulk RNA-sequencing (RNA-seq) data. Various methods have been proposed recently, yet their capabilities and limitations have not been evaluated systematically. A general guideline leading the research community through cell type deconvolution is missing. We developed a systematic approach for benchmarking such computational methods and assessed the accuracy of tools for estimating a variety of immune cell types from bulk RNA-seq samples. We used a single-cell RNA-seq dataset of ~11,000 cells from the tumor microenvironment to simulate bulk samples of known cell type proportions, which allowed us to measure the accuracy of the computational methods. Moreover, we collected publicly available data that provide both RNA-seq and independent, gold-standard estimates of the cell type proportions. This allowed us to analyze and condense the results of a hundred of thousand predictions to provide an exhaustive evaluation across computational methods over ten cell types and ~1,400 samples from five simulated and real-world datasets. We demonstrate that computational deconvolution performs at high accuracy for well-defined high-quality signatures, demonstrating its practical utility of bulk RNA-seq to dissect immune-cell composition of tumor samples. In addition to guidelines for method selection (depending on the cell types of interest) we also offer an R package to allow the community to perform integrated deconvolution using different methods themselves (https://grst.github.io/immunedeconv). We suggest that future efforts should be dedicated to refining cell population definitions and finding reliable signatures.