Exhibit 99.1

Nautilus, Inc. Appoints New Chief Executive Officer and

New Non-Executive Chairman of the Board

New Chief Executive Officer Has Extensive Experience in Profitably Growing Leading Consumer Brands

New Non-Executive Chairman Served in Key Executive Positions for Fortune 500 Consumer Companies

VANCOUVER, Washington, May 26, 2011 – Nautilus, Inc. (NYSE: NLS) today announced that its Board of Directors has named Bruce M. Cazenave as Chief Executive Officer and M. Carl Johnson, III has been elected Non-Executive Chairman of the Board. Mr. Edward J. Bramson has relinquished his role as Chief Executive Officer and Chairman of the Board and resigned from the board effective May 26, 2011.

“We are pleased to have two exceptional executives lead Nautilus forward in the roles of chief executive officer and non-executive chairman now that our operational and financial turnaround is complete,” stated Bramson, Chairman and Chief Executive Officer of Nautilus, Inc. “Bruce and Carl bring an extensive track record of successfully creating and building multi-billion dollar consumer brands. Their key leadership roles with consumer products companies that are moving forward from their turnaround phase to sustained profitable growth is an ideal fit for Nautilus. I believe their backgrounds, combined with the current management talent at Nautilus, will further strengthen the company’s ability to become a leading global fitness products company.”

Mr. Bramson continued, “I joined Nautilus as Chairman in late 2007 and became Chief Executive Officer in April 2008. During this time, the Nautilus team has achieved a remarkable transformation despite the difficult economic and consumer credit headwinds. We believe the company is now well positioned to move forward and to continue to capitalize on its achievements thus far.”

Mr. Cazenave brings to Nautilus over 20 years of senior executive leadership and an extensive background running divisions of premier global consumer products companies. He previously served in several key executive roles, all with a focus on profitable growth, including Vice President / G.M. at Black and Decker, Chief Operating Officer for Timberland - Europe, and President and CEO of Dorel Juvenile Group, a leading provider of children’s products and a subsidiary of Dorel Industries. More recently, Mr. Cazenave served as President of Central Garden and Pet’s Garden Décor Group.

1

Mr. Cazenave said, “I am very pleased with the opportunity to join Nautilus as its new CEO. The Company offers many of the leading products and brands in the fitness industry and has a proud history of innovation, outstanding talent and a strong operational foundation. During my career, I have had the opportunity to create and dramatically expand strong global consumer brands and I believe Nautilus possesses many of the necessary characteristics to achieve strong growth along with excellent financial and operational results. I am honored to join its leadership team and Board of Directors and to help drive the further success of the business.”

Mr. M. Carl Johnson, III will become Non-Executive Chairman of the Company’s Board of Directors. Mr. Johnson joined the Nautilus board in 2010 after holding key executive positions at Campbell Soup Company and Kraft USA. Mr. Johnson is currently a member of the Compensation Committee at Nautilus, Inc. From 2001 until his retirement in April 2011, Mr. Johnson served as Senior Vice President and Chief Strategy Officer of the Campbell Soup Company, where he had direct responsibility for corporate strategy, research & development, quality, corporate marketing services, licensing and e-Business. Mr. Johnson joined Campbell from Kraft Foods, where he ran three successively larger business divisions. From 1993 to 1995, Mr. Johnson served as Executive Vice President, Kraft Foods USA and General Manager of the $900 million Specialty Products Division. From 1995 to 1997, he served as Executive Vice President, Kraft Foods N.A. and President of the $1.5 billion Meals Division. In 1997, Mr. Johnson was named Executive Vice President, Kraft Foods N.A. and President of the $2.5 billion New Meals (Meals and Enhancers) Division and a member of the Kraft Foods Operating Committee, and served in these positions until early 2001.

The Company also announced that Craig L. McKibben, appointed to the Nautilus Board of Directors in 2009, has also tendered his resignation from the board effective May 26, 2011. Mr. McKibben has, since 2002, been a Managing Director, Partner and the Chief Financial Officer of Sherborne Investors LP, Sherborne Investors Management LP and certain of their affiliates.

About Nautilus, Inc.

Headquartered in Vancouver, Wash., Nautilus, Inc. (NYSE: NLS) is a global fitness products company providing innovative, quality solutions to help people achieve a healthy lifestyle. With a brand portfolio including Nautilus®, Bowflex®, Schwinn® Fitness, and Universal®, the Company markets innovative fitness products through direct and retail channels. Website: www.nautilusinc.com.

Safe Harbor Statement

This press release includes forward-looking statements (statements which are not historical facts) within the meaning of the Private Securities Litigation Reform Act of 1995. Factors that could cause Nautilus, Inc.’s actual results to differ materially from these forward-looking statements include our ability to acquire inventory from sole source foreign manufacturers at acceptable costs, within timely delivery schedules and that meet our quality control standards, availability and price of media time consistent with our cost and audience profile parameters, a decline in consumer spending due to unfavorable economic conditions, an adverse change in the availability of credit for our customers who finance their purchases, our ability to pass along

2

vendor raw material price increases and increased shipping costs, our ability to effectively develop, market and sell future products, our ability to protect our intellectual property, the introduction of competing products and our ability to get foreign-sourced product through customs in a timely manner. Additional assumptions, risks and uncertainties are described in detail in our registration statements, reports and other filings with the Securities and Exchange Commission, including the “Risk Factors” set forth in our Annual Report on Form 10-K, as supplemented by our quarterly reports on Form 10-Q. Such filings are available on our website or at www.sec.gov. You are cautioned that such statements are not guarantees of future performance and that actual results or developments may differ materially from those set forth in the forward-looking statements. We undertake no obligation to publicly update or revise forward-looking statements to reflect subsequent events or circumstances.

Investor Relations Contact:

John Mills, Senior Managing Director at ICR, LLC

Telephone: (310) 954-1105

3