Existing rate adaptation algorithms can broadly be classified under two categories: (a) signal to noise ratio measurement based and (b) statistical count based. While the former suffers from inaccurate estimations, the latter utilizes pre-defined thresholds for dynamically varying the rate. In this paper, we first analyze the impact of transmission rate on the performance of a wireless link as the performance may either improve or deteriorate with increasing transmission rates. Based on this observation, we then propose stochastic automata rate adaptation algorithm (SARA). SARA is inspired by stochastic learning automata (SLA), a machine learning technique for adaptation in random environments. SARA assigns a selection probability to each of the transmission rates. It then randomly selects a rate for a transmission attempt and dynamically updates the probabilities based on the obtained feedback from the receiver (ACK/NACK), thereby obviating the need for explicit channel estimation or predefined thresholds. As opposed to the previous work, SARA is ideally suited for both stationary and non-stationary channel environments and is fully compatible with the existing IEEE 802.11 MAC standard. We compare the performance of our proposed protocol with automatic rate fallback (ARF) thoroughly and adaptive ARF (AARF) and other existing protocols, under different channel scenarios.