The aim of this work was to design and evaluate effervescent floating gastro-retentive drug delivery matrix tablets with sustained-release behavior using a binary mixture of hydroxyethyl cellulose and sodium alginate. Pentoxifylline was used as a highly water-soluble, short half-life model drug with a high density. The floating capacity, swelling, and drug release behaviors of drug-loaded matrix tablets were evaluated in 0.1 N HCl (pH 1.2) at 37°C±0.5°C. Release data were analyzed by fitting the power law model of Korsmeyer–Peppas. The effect of different formulation variables was investigated, such as wet granulation, sodium bicarbonate gas-forming agent level, and tablet hardness properties. Statistical analysis was applied by paired sample t-test and one-way analysis of variance depending on the type of data to determine significant effect of different parameters. All prepared tablets through wet granulation showed acceptable physicochemical properties and their drug release profiles followed non-Fickian diffusion. They could float on the surface of dissolution medium and sustain drug release over 24 hours. Tablets prepared with 20% w/w sodium bicarbonate at 50–54 N hardness were promising with respect to their floating lag time, floating duration, swelling ability, and sustained drug release profile.