We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs.We show that if the CLB has b bases, a tree network with n nodes can be mapped in O(C?n2b-1) time, where C is a function dependent on b. b is fixed for a given CLB architecture. In particular, this algorithm runs in O(n5) time when mapping a circuit of n nodes onto the Xilinx XC4000.To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any non-trivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n3) algorithm.The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.