In this paper we present a new Kalman filter extension for state update called Partitioned Update Kalman Filter (PUKF). PUKF updates the state using multidimensional measurements in parts. PUKF evaluates the nonlinearity of the measurement function within a Gaussian prior by comparing the effect of the 2nd order term on the Gaussian measurement noise. A linear transformation is applied to measurements to minimize the nonlinearity of a part of the measurement. The measurement update is then applied using only the part of the measurement that has low nonlinearity and the process is then repeated for the updated state using the remaining part of the transformed measurement until the whole measurement has been used. PUKF does the linearizations numerically and no analytical differentiation is required. Results show that when the measurement geometry allows effective partitioning, the proposed algorithm improves estimation accuracy and produces accurate covariance estimates.