This article derives the first analytical pricing formulas for American-style Asian options of the so-called floating strike type. Geometric as well as arithmetic averaging is considered. The setup is a standard Black-Scholes framework where the price of the underlying security evolves according to a geometric Brownian motion. A decomposition result that splits up the value of the floating strike American option into the price of an otherwise equivalent European option and an early exercise premium is first presented. This decomposition result is then manipulated further for the two separate types of averaging. With geometric averaging we derive an exact pricing formula, whereas with arithmetic averaging we develop an analytical approximation formula that proves to be very precise. Numerical examples are provided.