Abstract: The proper orthogonal decomposition (POD) is known as an effective model order reduction method to solve the transient nonlinear heat conduction problems. Although the execution-time economy in the solution of the equations coming from the significant drop in the number of degrees of freedom (DOFs) of the original finite element discretized system, the expected reduction in the overall computational times are not generally realized. The reason is that the solution of the nonlinear reduced order model involves an iterative procedure for which the global stiffness matrix needs to be reassembled in the original high dimensional space and then to be multiplied by the POD mode matrix at every time step. In order to mitigate this problem, a new and efficient algorithm is proposed in this paper to improve the computational efficiency of the POD-based reduced order model for a kind of transient nonlinear heat conduction problem in which the thermal conductivity of material is not a constant due to the change of temperature. Firstly, the element pre-conversation method (EPM) is used to compress the time for calculating the stiffness matrix of low dimensional system. Secondly, the multi-level linearization method (MLM) is used to eliminate the time-consuming procedure of iteration. Lastly, a hypothetical element matrix is constructed to effectively combine the EPM and the MLM for reducing the overall computational time to a great extent. Both 2D and 3D numerical examples are conducted to verify the accuracy and effectiveness of the proposed new algorithm by comparing its results with those of the finite element full order model. It is quite clear that significant savings in computational time can be achieved by this algorithm while maintaining an acceptable level of accuracy. The results show that: (1) the root mean square error (RMSE) of POD solutions decreases rapidly and stabilizes below 0.01% after a slight fluctuation in the initial short time, and the computational efficiency can be improved by 2~3 orders of magnitude when the DOFs of the problem under consideration is less than 6000; (2) the new algorithm works out the problem of poor acceleration of the conventional algorithm in solving nonlinear reduced order model, the computational effort saving can be seen clearly even for small problems and more pronounced for larger problems; (3) the truncated POD modes determined under simple constant thermal boundary conditions can be directly applied to obtain the reduced order model of the transient nonlinear heat conduction problems with the same geometric domain but a variety of complex smooth/unsmooth time-varying thermal boundary conditions and to predict the corresponding temperature fields quickly and accurately, which is valuable for engineering application.