The particle filter (PF) and the ensemble Kalman filter (EnKF) are two promising and popularly adopted types of ensemble-based data assimilation methods for paleoclimate reconstruction. However, no systematic comparison between them has been attempted. We compare these two uncertainty based methods in pseudo proxy experiments where synthetic seasonal mean sea surface temperature (SST) observations are assimilated. Their skills are evaluated with regards to local, hemispherically- and globally-averaged analysis error, and their ability to capture large-scale modes of variability. It is found that the EAKF (Ensemble Adjstment Kalman Filter, a variant of EnKF) performs better than the PF with only one third of the ensemble size, despite PF's theoretical superiority in allowing for non-Gaussian statistics and nonlinear dynamics. The success of the EAKF is attributed to the facts that: 1) Gaussian assumption is somewhat appropriate for this application; 2) The EAKF is less sensitive to sampling errors than the PF due to the different methodological natures. 16 members are enough to estimate accurate covariance for the EAKF, but 48 (even 96) members still underrepresent the state space of high-dimensional system for the PF. Our study highlights the importance of a large localization radius in the application of the EnKF to paleoclimate reconstruction due to the sparse proxy network, and suggests that additional techniques, such as localization or clustered particle filter, are needed to improve the PF for paleoclimate reconstruction, in addition to the simple importance resampling currently adopted by most research.