Enceladus and possibly Europa spew materials from their internal ocean into their exosphere, some of which are deposited back onto the surface of those Ocean Worlds. This setting provides a unique opportunity to seek traces of past or extant life in ice plume deposits on their surfaces. However, the design of lander missions and surface sampling techniques, and the choice of sampling locations rely heavily on strength expectations. Here we present an experimental investigation of the evolution in strength of ice plume deposit analogs at several temperatures, as well as a model that predicts first-order estimates of the strength of evolved ice plume deposits under geologic timescales relevant to Enceladus and Europa. These results suggest that plume deposits remain weak and poorly consolidated on Enceladus, while they may develop substantial strength (comparable to solid ice) within < 100 My on Europa.