Simple, intuitive, and scalable to large problems, $k$-means clustering is perhaps the most frequently-used technique for unsupervised learning. However, global optimization of the $k$-means objective function is challenging, as the clustering algorithm is highly sensitive to its initial value. Exploiting the connection between $k$-means and Bayesian clustering, we explore the benefits of stochastic optimization to address this issue. Our "$\texttt{no means}$" algorithm has provably superior mixing time to a natural Gibbs sampler with auxiliary cluster centroids. Yet, it retains the same computational complexity as the original $k$-means approach. Comparisons on two benchmark datasets indicate that stochastic search usually produces more homogeneous clusters than the steepest descent algorithm employed by $k$-means. Our $\texttt{no means}$ method objective function has multiple modes which are not too far apart.