Aim: The present investigation deals with the formulation of floating-bioadhesive matrix tablets of verapamil hydrochloride (VH). The main objective of this work was to overcome the limitations of the conventional floating matrix tablets. Materials and Methods: Hydroxypropyl methylcellulose (HPMC) K15M was used as a matrix-forming agent whereas carboxymethyl tamarind gum (CMTG) was used to promote bioadhesion. Systematic optimization was performed using a central composite design with two independent variables and six dependent variables. Tablets were prepared by using the wet granulation method. The effect of polymer ratio (HPMC:CMTG) and sodium bicarbonate (SB) concentration on the total floating time (TFT), floating lag time (FLT), bioadhesion, swelling, and drug release (DR) was studied and optimized. Results and Discussion: Floating-bioadhesive matrix tablets of VH showed good physicochemical properties. The FLT was within the range of 2.87-14.41 min and TFT was more than 12 h. The tablets showed 17-30% of burst release in the 1st h and controlled release over a period of 12-h. DR and swelling were significantly (P < 0.05) affected by polymer ratio and concentration of SB in formulation. The polynomial mathematical models, generated for various response variables using multiple regression analysis, were found to be statistically significant (P < 0.05). Optimized batch showed FLT of 6.14 min, bioadhesion of 17.23 g, swelling of 74.83% at 5 h, and DR of 75.48% at 10 h, with anomalous release mechanism. The observed values were near to the predicted values obtained by the experimental design. Conclusion: The floating-bioadhesive tablets of VH prepared using HPMC and CMTG exhibited a potential to retain and control the release of drug in stomach for more than 12 h and may be used as an alternative to the conventional floating tablets of VH.