An efficient algorithm is proposed for the solution of multiparametric convex nonlinear problems (NLPs). Based on an outer-approximation algorithm, the proposed iterative procedure involves the solution of deterministic NLP subproblems and master multiparametric linear problems, with which an epsilon-approximate parametric solution profile can be defined. The procedure is guided by several heuristics that significantly reduce the number of primal subproblems solved and the complexity of the master problems. The applicability of the procedure is demonstrated through different variations of problems taken from the open literature, which serve to explain the algorithm in detail and compare its performance with those of previous approaches.