In the ensemble Kalman filter (EnKF), uncertainty in the state of a dynamical model is represented as samples of the state vector. The samples are propagated forward using the evolution model, and the forecast (prior) mean and covariance matrix are estimated from the ensemble. Data assimilation is carried out by using these estimates in the Kalman filter formulas. The prior is given in the subspace spanned by the propagated ensemble, the size of which is typically much smaller than the dimension of the state space. The rank-deficiency of these covariance matrices is problematic, and, for instance, unrealistic correlations often appear between spatially distant points, and different localization or covariance tapering methods are needed to make the approach feasible in practice. In this paper, we present a novel way to implement ensemble Kalman filtering using optimization-based sampling, in which the forecast error covariance has full rank and the need for localization is diminished. The method is based on the randomize then optimize (RTO) technique, where a sample from a Gaussian distribution is computed by perturbing the data and the prior, and solving a quadratic optimization problem. We test our method in two benchmark problems: the 40-dimensional Lorenz '96 model and the 1600-dimensional two-layer quasi-geostrophic model. Results show that the performance of the method is significantly better than that of the standard EnKF, especially with small ensemble sizes when the rank-deficiency problems in EnKF are emphasized.