Determining unknown boundary conditions or material properties in heat transfer problems can be performed by solving inverse heat transfer problems. Solving inverse problems is an optimization problem. The inverse problems are ill-posed, and their accuracy is highly sensitive to the number and location of the sensors, as well as the selected optimization technique. Therefore, the development of new methods that are more stable to solve heat transfer inverse problems has always been of interest. In this paper, a new method is introduced to solve the inverse problems based on the Regression Tree (RT) methods. A new class in RT’s are introduced in which we try to fit a linear regression function on each leaf node as compared to classic RT’s where only a simple average value of data points assigned to each leaf is calculated to improve the accuracy of the fitted models. We call this new class of RT as Trended RT (TRT). Besides TRT, a modified version of TRT, Bounded TRT (BTRT), is also used in the present study which the regressed line is bounded to observed limits on dependent variable. To investigate the method’s efficiency in handling inverse heat transfer problems, the estimation of three different types of boundary conditions in the steady-state heat transfer problem of a steel plate, using the temperature of specific points, is considered. The effects of the number and the location of sensors on the performance of the mentioned methods are also investigated.