Wnt ligands are considered classical morphogens, for which the strength of the cellular response is proportional to the concentration of the ligand. Herein, we show an emergent property of bistability arising from feedback among the Wnt destruction complex proteins that target the key transcriptional co-activator β-catenin for degradation. Using biochemical reconstitution, we identified positive feedback between the scaffold protein Axin and the kinase glycogen synthase kinase 3 (GSK3). Theoretical modeling of this feedback between Axin and GSK3 suggested that the activity of the destruction complex exhibits bistable behavior. We experimentally confirmed these predictions by demonstrating that cellular cytoplasmic β-catenin concentrations exhibit an “all-or-none” response with sustained memory (hysteresis) of the signaling input. This bistable behavior was transformed into a graded response and memory was lost through inhibition of GSK3. These findings provide a mechanism for establishing decisive, switch-like cellular response and memory upon Wnt pathway stimulation.