This paper develops a comprehensive approach to the definition of transportation analysis zones (TAZ), and therein, presents a new methodology and algorithm for the definition of TAZ embedded in geographic information systems software, improves the base algorithm with several local algorithms, and comprehensively analyses the obtained results. The results obtained are then compared to these presently used in the transportation analysis process of the Lisbon Metropolitan Area. The proposed algorithm presents a new methodology for TAZ design based on a smoothed density surface of geocoded travel demand data. The algorithm aims to minimise the loss of information when moving from a continuous representation of the origin and destination of each trip to their discrete representations through zones, and focuses on the trade-off between the statistical precision, geographical error, and the percentage of intra-zonal trips of the resulting OD matrix. The results for the Lisbon Metropolitan Area case study suggest a significant improvement in OD matrix estimates compared to current transportation analysis practises based on administrative units.